package sol.leetcode;

/**
 * Unique Binary Search Trees
 */
public class Issue096 {
    public int numTrees(int n) {
        return count(n, new int[n]);
    }

    int count(int n, int[] storage) {
        if (n <= 1)
            return 1;
        if (storage[n - 1] > 0)
            return storage[n - 1];

        int sum = 0;
        for (int i = 1; i <= n; ++i)
            sum += count(i - 1, storage) * count(n - i, storage);

        storage[n - 1] = sum;
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new Issue096().numTrees(3));
    }
}
